import java.util.LinkedList;
import java.util.Scanner;

public class Test {
    //数组nums包含从0到n的所有整数，但其中缺了一个数字，编写代码找出缺失的整数，时间复杂度O（n)
    //输入：[9, 6, 4, 2, 3, 5, 7, 0, 1]
    //输出：8
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int sum = (1 + n) * n / 2;
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            s += nums[i];
        }
        int num = sum - s;
        System.out.println(num);
    }
    //OJ解法
//    class Solution {
//        public int missingNumber(int[] nums) {
//            int n=nums.length;
//            int sum=(n+1)*n/2;
//            int sum1=0;
//            for(int i:nums){
//                sum1+=i;
//            }
//            int s=0;
//            s=sum-sum1;
//            return s;
//        }
//    }
    //————————————————————————————————————————————————————————
    //给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
//    输入: nums = [1,2,3,4,5,6,7], k = 3
//    输出: [5,6,7,1,2,3,4]
//    解释:
//    向右轮转 1 步: [7,1,2,3,4,5,6]
//    向右轮转 2 步: [6,7,1,2,3,4,5]
//    向右轮转 3 步: [5,6,7,1,2,3,4]

//    class Solution {
//        public void rotate(int[] nums, int k) {
//            k %= nums.length;//k 大于数组长度时，旋转 k 次等价于旋转 k % nums.length 次
//            for(int i = 0; i < k; ++i){
//                // 将数组中前n-1个元素整体往后搬移一个位置
//                int last = nums[nums.length-1];
//                for(int j = nums.length-1; j >= 1; --j){
//                    nums[j] = nums[j-1];
//                }
//                // 将搬移前最后一个元素放到数组0号位置
//                nums[0] = last;
//            }
//        }
//    }
//*/

    /*
      解题思路：使用三次逆转法，让数组旋转k次
        1. 整体逆置
        2. 逆转子数组[0, k - 1]
        3. 逆转子数组[k, size - 1]
    */
//    class Solution {
//        void rotate(int[] nums, int left, int right){
//            while(left < right){
//                int temp = nums[left];
//                nums[left] = nums[right];
//                nums[right] = temp;
//                left++;
//                right--;
//            }
//        }
//        public void rotate(int[] nums, int k) {
//            k %= nums.length;
//            rotate(nums, 0, nums.length-1);
//            rotate(nums, 0, k-1);
//            rotate(nums, k, nums.length-1);
//        }
//    }


    //——————————————————————————————————————————————————————————
    //一个数组 nums 和一个值 val，需要原地移除所有数值等于val的元素，元素的顺序可能发生改变，
    // 然后返回 nums 中与 val 不同的元素的数量
//    输入：nums = [3,2,2,3], val = 3
//    输出：2, nums = [2,2,_,_]
    public static void main2(String[] args) {
        int[] nums={3,2,2,3,1};
        Scanner scanner=new Scanner(System.in);
        int val=scanner.nextInt();
        int j=0;
        for (int i = 0; i <nums.length ; i++) {
            if(nums[i]!=val) {
                nums[j] = nums[i];
                j++;
            }
        }
        for (int k = 0; k < j; k++) {
            System.out.print(nums[k] + " ");
        }
        System.out.println();
        System.out.println(j);
    }
    //OJ解法
//    class Solution {
//        public int removeElement(int[] nums, int val) {
//            int j = 0;
//            for (int i = 0; i < nums.length; i++) {
//                if (nums[i] != val) {
//                    nums[j] = nums[i];
//                    j++;
//                }
//            }
//            return j;
//        }
//    }
    //——————————————————————————————————————————————————————————
    //一个非严格递增排列的数组nums ，原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度
    // 元素的相对顺序应该保持一致,然后返回 nums 中唯一元素的个数
//    输入：nums = [1,1,2]，nums = [0,0,1,1,1,2,2,3,3,4]
//    输出：2, nums = [1,2,_]
    public static void main3(String[] args) {
        int[] nums={1,1,2};
        if(nums.length==0){
            return;
        }
        int j=1;
        for (int i =1; i <nums.length ; i++) {
            if(nums[i]!=nums[j-1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        System.out.println(j);
        for (int k = 0; k<j ; k++) {
            System.out.print(nums[k]+" ");
        }
        System.out.println();
    }
    //OJ解法
//    class Solution {
//        public int removeDuplicates(int[] nums) {
//            if (nums.length == 0) {
//                return 0;
//            }
//            int k = 1;
//            for (int i = 1; i < nums.length; i++) {
//                if (nums[i] != nums[k - 1]) {
//                    nums[k] = nums[i];
//                    k++;
//                }
//            }
//            return k;
//        }
//    }
}
